import java.util.ArrayList;
/**
 * 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序.
 * 输入：9 -> 返回值: [[2,3,4],[4,5]]
 * 输入：0 -> 返回值：[]
 *
 * 链接: https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 *
 * Date: 2022-10-15
 * Time: 21:25
 */
public class Solution {
    public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(sum <= 2) return result;

        int low = 1;
        int height = 2;
        // 在[1,S]区间找符合条件的连续正数序列.
        while(low < height) {
            // 等差数列求和公式: (a0 + an) * n / 2
            int total = ( (low + height)*(height - low + 1) )>> 1;
            if(total < sum) {
                ++height;
            } else if(total == sum) {
                // 找到了一组序列
                ArrayList<Integer> tmp = new ArrayList<>();
                for(int i = low; i <= height; ++i) {
                    tmp.add(i);
                }
                result.add(tmp);
                ++low;
            } else {
                ++low;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // [[2,3,4],[4,5]]
        System.out.println(FindContinuousSequence(9));
    }
}